package com.extractor;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created by IntelliJ IDEA.
 * User: Administrator
 * Date: Jul 28, 2010
 * Time: 9:34:59 AM
 * To change this template use File | Settings | File Templates.
 */
public class AlgorithmMAS {
    public static final int K = 1000000000;
    public static final int MAXIMUM_WASTE_ALLOWED = 15;


    public RatioOutputs findRatios(int noOfPiles, int maxRatioSum, String style, String cw, ArrayList<Integer> quantities) {
        RatioOutputs ro = new RatioOutputs();

        ro.STYLE = style;
        ro.CW = cw;

        int loopCount;

        /*round 1*/
        ro.piles1 = calculatePileSizeForThisRound(noOfPiles, quantities);
        ro.ratios1 = calculateRatiosAccordingToMinimumValue(quantities);
        if (checkFinished(ro.piles1, quantities, ro.ratios1)) {
            return ro;
        } else {
            loopCount = 0;
            while (maxRatioSum < getTotal(ro.ratios1)) {
                ro.ratios1 = refine(ro.ratios1, maxRatioSum, quantities);
                loopCount++;
                if (10 < loopCount) {
                    break;
                }
            }
            if (checkFinished(ro.piles1, quantities, ro.ratios1)) {
                return ro;
            } else {
                ro.piles1 = findRatiosWithinMaximumWastageByIncreasingPileSize(ro.piles1, quantities, ro.ratios1, ro);
                if (checkFinished(ro.piles1, quantities, ro.ratios1)) {
                    return ro;
                } else {
                    int k = 1;
                    loopCount = 0;
                    while (getTotal(ro.ratios1) < maxRatioSum) {
                        k++;
                        ArrayList<Integer> ret;
                        ret = refineRatiosToMaximumMultiple(ro.piles1, quantities, ro.ratios1, maxRatioSum, k);
                        if (ret.equals(ro.ratios1)) {
                            break;
                        } else {
                            ro.ratios1 = ret;
                        }
                        if (10 < loopCount) {
                            break;
                        }
                    }
                    if (checkFinished(ro.piles1, quantities, ro.ratios1)) {
                        return ro;
                    } else {
                        while (getTotal(ro.ratios1) < maxRatioSum) {
                            ro.ratios1 = refineRatiosByMinimumWaste(ro.piles1, quantities, ro.ratios1, maxRatioSum);
                        }
                        if (checkFinished(ro.piles1, quantities, ro.ratios1)) {
                            return ro;
                        }
                    }
                }
            }
        }


        /*round 2*/
        ro.quantitiesForRatios2 = calculateQuantitiesForNextStep(ro.piles1, quantities, ro.ratios1);
        ro.piles2 = calculatePileSizeForThisRound(noOfPiles, ro.quantitiesForRatios2);
        ro.ratios2 = calculateRatiosAccordingToMinimumValue(ro.quantitiesForRatios2);
        if (checkFinished(ro.piles2, ro.quantitiesForRatios2, ro.ratios2)) {
            return ro;
        } else {
            loopCount = 0;
            while (maxRatioSum < getTotal(ro.ratios2)) {
                ro.ratios2 = refine(ro.ratios2, maxRatioSum, ro.quantitiesForRatios2);
                loopCount++;
                if (10 < loopCount) {
                    break;
                }
            }
            if (checkFinished(ro.piles2, ro.quantitiesForRatios2, ro.ratios2)) {
                return ro;
            } else {
                ro.piles2 = findRatiosWithinMaximumWastageByIncreasingPileSize(ro.piles2, ro.quantitiesForRatios2, ro.ratios2, ro);
                if (checkFinished(ro.piles2, ro.quantitiesForRatios2, ro.ratios2)) {
                    return ro;
                } else {
                    int m = 1;
                    loopCount = 0;
                    while (getTotal(ro.ratios2) < maxRatioSum) {
                        m++;
                        ArrayList<Integer> ret;
                        ret = refineRatiosToMaximumMultiple(ro.piles2, ro.quantitiesForRatios2, ro.ratios2, maxRatioSum, m);
                        if (ret.equals(ro.ratios2)) {
                            break;
                        } else {
                            ro.ratios2 = ret;
                        }
                        if (10 < loopCount) {
                            break;
                        }
                    }
                    if (checkFinished(ro.piles2, ro.quantitiesForRatios2, ro.ratios2)) {
                        return ro;
                    } else {
                        while (getTotal(ro.ratios2) < maxRatioSum) {
                            ro.ratios2 = refineRatiosByMinimumWaste(ro.piles2, ro.quantitiesForRatios2, ro.ratios2, maxRatioSum);
                        }
                        if (checkFinished(ro.piles2, ro.quantitiesForRatios2, ro.ratios2)) {
                            return ro;
                        }
                    }
                }
            }
        }


        /*round 3*/
        ro.quantitiesForRatios3 = calculateQuantitiesForNextStep(ro.piles2, ro.quantitiesForRatios2, ro.ratios2);
        ro.piles3 = calculatePileSizeForThisRound(noOfPiles, ro.quantitiesForRatios3);
        ro.ratios3 = calculateRatiosAccordingToMinimumValue(ro.quantitiesForRatios3);
        if (checkFinished(ro.piles3, ro.quantitiesForRatios3, ro.ratios3)) {
            return ro;
        } else {
            loopCount = 0;
            while (maxRatioSum < getTotal(ro.ratios3)) {
                ro.ratios3 = refine(ro.ratios3, maxRatioSum, ro.quantitiesForRatios3);
                loopCount++;
                if (10 < loopCount) {
                    break;
                }
            }
            if (checkFinished(ro.piles3, ro.quantitiesForRatios3, ro.ratios3)) {
                return ro;
            } else {
                ro.piles3 = findRatiosWithinMaximumWastageByIncreasingPileSize(ro.piles3, ro.quantitiesForRatios3, ro.ratios3, ro);
                if (checkFinished(ro.piles3, ro.quantitiesForRatios3, ro.ratios3)) {
                    return ro;
                } else {
                    int n = 1;
                    loopCount = 0;
                    while (getTotal(ro.ratios3) < maxRatioSum) {
                        n++;
                        ArrayList<Integer> ret;
                        ret = refineRatiosToMaximumMultiple(ro.piles3, ro.quantitiesForRatios3, ro.ratios3, maxRatioSum, n);
                        if (ret.equals(ro.ratios3)) {
                            break;
                        } else {
                            ro.ratios3 = ret;
                        }
                        if (10 < loopCount) {
                            break;
                        }
                    }
                    if (checkFinished(ro.piles3, ro.quantitiesForRatios3, ro.ratios3)) {
                        return ro;
                    } else {
                        while (getTotal(ro.ratios3) < maxRatioSum) {
                            ro.ratios3 = refineRatiosByMinimumWaste(ro.piles3, ro.quantitiesForRatios3, ro.ratios3, maxRatioSum);
                        }
                        if (checkFinished(ro.piles3, ro.quantitiesForRatios3, ro.ratios3)) {
                            return ro;
                        }
                    }
                }
            }
        }


        /*round 4*/
        ro.quantitiesForRatios4 = calculateQuantitiesForNextStep(ro.piles3, ro.quantitiesForRatios3, ro.ratios3);
        ro.piles4 = calculatePileSizeForThisRound(noOfPiles, ro.quantitiesForRatios4);
        ro.ratios4 = calculateRatiosAccordingToMinimumValue(ro.quantitiesForRatios4);
        if (checkFinished(ro.piles4, ro.quantitiesForRatios4, ro.ratios4)) {
            return ro;
        } else {
            loopCount = 0;
            while (maxRatioSum < getTotal(ro.ratios4)) {
                ro.ratios4 = refine(ro.ratios4, maxRatioSum, ro.quantitiesForRatios4);
                loopCount++;
                if (10 < loopCount) {
                    break;
                }
            }
            if (checkFinished(ro.piles4, ro.quantitiesForRatios4, ro.ratios4)) {
                return ro;
            } else {
                ro.piles4 = findRatiosWithinMaximumWastageByIncreasingPileSize(ro.piles4, ro.quantitiesForRatios4, ro.ratios4, ro);
                if (checkFinished(ro.piles4, ro.quantitiesForRatios4, ro.ratios4)) {
                    return ro;
                } else {
                    int p = 1;
                    loopCount = 0;
                    while (getTotal(ro.ratios4) < maxRatioSum) {
                        p++;
                        ArrayList<Integer> ret;
                        ret = refineRatiosToMaximumMultiple(ro.piles4, ro.quantitiesForRatios4, ro.ratios4, maxRatioSum, p);
                        if (ret.equals(ro.ratios4)) {
                            break;
                        } else {
                            ro.ratios4 = ret;
                        }
                        if (10 < loopCount) {
                            break;
                        }
                    }
                    if (checkFinished(ro.piles4, ro.quantitiesForRatios4, ro.ratios4)) {
                        return ro;
                    } else {
                        while (getTotal(ro.ratios4) < maxRatioSum) {
                            ro.ratios4 = refineRatiosByMinimumWaste(ro.piles4, ro.quantitiesForRatios4, ro.ratios4, maxRatioSum);
                        }
                        if (checkFinished(ro.piles4, ro.quantitiesForRatios4, ro.ratios4)) {
                            return ro;
                        } else {
                            ro.finished = false;
                        }
                    }
                }
            }
        }

        return ro;
    }

    private int findRatiosWithinMaximumWastageByIncreasingPileSize(int piles, ArrayList<Integer> quantities, ArrayList<Integer> ratios, RatioOutputs ro) {
        int tempWaste;
        int tempPiles = piles;
        do {
            piles++;
            tempWaste = 0;
            for (int i = 0; i < quantities.size(); i++) {
                int val1 = quantities.get(i);
                int val2 = ratios.get(i);
                if (val1 != AlgorithmMAS.K) {
                    int wastage = piles * val2 - val1;
                    if (0 < wastage) {
                        tempWaste += wastage;
                    }
                }
            }
        } while (tempWaste + ro.waste < MAXIMUM_WASTE_ALLOWED && !checkFinished(piles, quantities, ratios));
        if (!(tempWaste + ro.waste < MAXIMUM_WASTE_ALLOWED)) {
            return tempPiles;
        } else {
            ro.waste += tempWaste;
            return piles;
        }
    }

    private boolean checkFinished(int piles, ArrayList<Integer> quantities, ArrayList<Integer> ratios) {
        ArrayList<Integer> data = calculateQuantitiesForNextStep(piles, quantities, ratios);
        boolean result = true;
        for (int val : data) {
            result = val == AlgorithmMAS.K;
            if (!result) break;
        }
        return result;
    }

    private ArrayList<Integer> refineRatiosByMinimumWaste(int piles, ArrayList<Integer> quantitiesForRatios, ArrayList<Integer> ratios, int maxRatioSum) {
        int index = getIndexOfRatioHavingMinimumWaste(piles, quantitiesForRatios, ratios);
        int valR = ratios.get(index);
        ratios.set(index, valR + 1);
        return ratios;
    }

    private ArrayList<Integer> refineRatiosToMaximumMultiple(int pilesSize, ArrayList<Integer> quantities, ArrayList<Integer> ratios, int maxRatioSum, int coefficient) {
        ArrayList<Integer> out = new ArrayList<Integer>();
        for (int i = 0; i < ratios.size(); i++) {
            int val = ratios.get(i);
            int l = (K != val) ? (val * coefficient) / (coefficient - 1) : K;
            out.add(l);
        }
        ratios = (getTotal(out) <= maxRatioSum && noWastage(out, pilesSize, quantities)) ? out : ratios;
        return ratios;
    }

    private boolean noWastage(ArrayList<Integer> out, int pilesSize, ArrayList<Integer> quantities) {
        boolean noWasting = true;
        for (int i = 0; i < out.size(); i++) {
            int val1 = quantities.get(i);
            int val2 = out.get(i);
            if (val1 != K) {
                noWasting = val2 * pilesSize < val1;
                if (!noWasting) {
                    break;
                }
            }
        }
        return noWasting;
    }

    private int getIndexOfRatioHavingMinimumWaste(int pilesSize, ArrayList<Integer> quantities, ArrayList<Integer> ratios) {
        int resultIndex = 0;
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for (int i = 0; i < quantities.size(); i++) {
            int originalQuantity = quantities.get(i);
            int ratioValue = ratios.get(i);
            if (originalQuantity != K && ratioValue != K) {
                int calculatedWaste = ((ratioValue + 1) * pilesSize) - originalQuantity;
                temp.add(calculatedWaste);
            } else {
                temp.add(K);
            }

        }
        int minimumWastage = Collections.min(temp);
        resultIndex = temp.indexOf(minimumWastage);
        return resultIndex;
    }

    private ArrayList<Integer> calculateQuantitiesForNextStep(int noOfPiles, ArrayList<Integer> quantities, ArrayList<Integer> ratios) {
        ArrayList<Integer> out = new ArrayList<Integer>();
        for (int i = 0; i < quantities.size(); i++) {
            int val1 = quantities.get(i);
            int val2 = ratios.get(i);
            int val3 = K;
            if (val1 != K && val2 != K) {
                int t = val1 - val2 * noOfPiles;
                val3 = t <= 0 ? K : t;
            } else if (val1 == K) {
                val3 = K;
            } else if (val2 == K) {
                val3 = val1;
            }
            out.add(val3);
        }
        return out;
    }

    private ArrayList<Integer> calculateRatiosAccordingToMinimumValue(ArrayList<Integer> one) {
        ArrayList<Integer> out = new ArrayList<Integer>();
        double minValue = (double) Collections.min(one);
        for (int i = 0; i < one.size(); i++) {
            int val = one.get(i);
            double value = 0;
            double div = 0;
            double result = 0;
            if (K != val) {
                value = (double) val;
                div = value / minValue;
                result = Math.floor(div);
            } else {
                result = K;
            }
            out.add((int) result);
        }
        return out;
    }

    private ArrayList<Integer> refine(ArrayList<Integer> ratios, int maxRatioSum, ArrayList<Integer> quantities) {
        int minValue = Collections.min(quantities);
        int minIndex = quantities.indexOf(minValue);
        /*int maxVal = getMaxValue(ratios);
        for (int i = 0; i < ratios.size(); i++) {
            int val = ratios.get(i);
            if (val != K) {
                if (maxRatioSum < maxVal / val) {*/
        ratios.set(minIndex, K);
        /*}
            }
        }*/
        //if(getTotal(ratios))
        return calculateRatiosAccordingToMinimumValue(ratios);
        //return ratios;
    }

    private int getMaxValue(ArrayList<Integer> ratios) {
        int max = 0;
        for (int val : ratios) {
            if (val == K) continue;
            max = (max < val) ? val : max;
        }
        return max;
    }

    private int getTotal(ArrayList<Integer> ratios1) {
        int total = 0;
        for (int i = 0; i < ratios1.size(); i++) {
            int val = ratios1.get(i);
            if (val != K) {
                total += ratios1.get(i);
            }
        }
        return total;
    }

    private int calculatePileSizeForThisRound(int noOfPiles, ArrayList<Integer> quantities) {
        int min = Collections.min(quantities);
        return min < noOfPiles ? min : noOfPiles;
    }
}
